"""
Functors for ring and modules of graded expansions.

AUTHOR :
    -- Martin Raum (2009 - 07 - 27) Initial version
"""

#===============================================================================
# 
# Copyright (C) 2009 Martin Raum
# 
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 3
# of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful, 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, see <http://www.gnu.org/licenses/>.
#
#===============================================================================

from itertools import groupby, dropwhile
from sage.algebras.algebra import Algebra
from sage.categories.morphism import Morphism
from sage.categories.pushout import ConstructionFunctor, pushout
from sage.categories.rings import Rings
from sage.misc.misc import prod
from sage.modules.module import Module 
from sage.rings.integer import Integer
from sage.structure.sequence import Sequence
import operator

#===============================================================================
# GradedExpansionFunctor
#===============================================================================

class GradedExpansionFunctor ( ConstructionFunctor ) :
    """
    Constructing a graded expansion ring or module from a base ring.
    """
    
    rank = 10
    
    def __init__( self, base_ring_generators, generators,
                  relations, grading, all_relations = True, reduce_before_evaluating = True ) :
        """
        INPUT:
        - ``base_ring_generators``      -- A sequence of (equivariant) monoid power series with
                                           coefficient domain the base ring of the coefficient
                                           domain of the generators or ``None``.
        - ``generators``                -- A sequence of (equivariant) monoid power series; The generators
                                           of the ambient over the ring generated by the base ring
                                           generators.
        - ``relations``                 -- An ideal in a polynomial ring with ``len(base_ring_generators) + len(generators)``
                                           variables.
        - ``grading``                   -- A grading deriving from :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_grading`;
                                           A grading for the polynomial ring of the relations.
        - ``all_relations``             -- A boolean (default: ``True``); If ``True`` the relations given
                                           for the polynomial ring are all relations that the Fourier
                                           expansion have.
        - ``reduce_before_evaluating``  -- A boolean (default: ``True``); If ``True`` any monomial
                                           will be Groebner reduced before the Fourier expansion
                                           is calculated.

        NOTE:
            The grading must respect the relations of the generators.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: funct = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
        """
        if grading.ngens() != relations.ring().ngens() :
            raise ValueError( "Grading must have the same number of variables as the relations' polynomial ring." )

        self.__relations = relations
        self.__grading = grading
        self.__all_relations = all_relations
        self.__reduce_before_evaluating = reduce_before_evaluating

        self.__gen_expansions = Sequence(generators)
        if base_ring_generators is None :
            self.__base_gen_expansions = Sequence([], universe = self.__gen_expansions.universe().base_ring())
        else :
            self.__base_gen_expansions = Sequence(base_ring_generators)

        if len(self.__base_gen_expansions) == 0 :
            scalar_ring = self.__gen_expansions.universe().base_ring()
            if self.__gen_expansions.universe().coefficient_domain() != self.__gen_expansions.universe().base_ring() :
                scalar_ring = self.__gen_expansions.universe().base_ring().base_ring()
            else :
                scalar_ring = self.__gen_expansions.universe().base_ring()
        else :
            scalar_ring = self.__base_gen_expansions.universe().base_ring()

        if not relations.base_ring().has_coerce_map_from(scalar_ring) :
            raise ValueError( "The generators must be defined over the base ring of relations" )

        if not isinstance(self.__gen_expansions.universe(), Algebra) and \
           not isinstance(self.__gen_expansions.universe(), Module) :
            raise TypeError( "The generators' universe must be an algebra or a module" )

        ConstructionFunctor.__init__( self, Rings(), Rings() )
        
    def __call__(self, R) :
        """
        The graded expansion ring with the given generators over the base
        ring `R`.
                
        INPUT:
            - `R` -- A ring.
        
        OUTPUT:
            An instance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_ambient.GradedExpansion_abstract`.
        
        NOTE:
            The ring of Fourier expansions given by the generators associated
            with this functor must admit a base extension to `R`.

        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_module import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: K.<rho> = CyclotomicField(6)
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: funct = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct(K)
            Graded expansion ring with generators b
            sage: m = FreeModule(QQ, 3)
            sage: mpsm = MonoidPowerSeriesModule(m, NNMonoid(False))
            sage: mps = mpsm.base_ring()
            sage: funct = GradedExpansionFunctor(None, Sequence([MonoidPowerSeries(mpsm, {1 : m([1,2,3]), 2 : m([3,-3,2])}, mpsm.monoid().filter(4)), MonoidPowerSeries(mpsm, {1 : m([2,-1,-1]), 2 : m([1,0,0])}, mpsm.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct(K)
            Graded expansion module with generators a, b
        """
        from gradedexpansion_ring import GradedExpansionRing_class
        from gradedexpansion_module import GradedExpansionModule_class
        
        R = pushout(self.__relations.ring(), R)
        rel = R.ideal(self.__relations.gens())
        
        if isinstance(self.__gen_expansions.universe(), Algebra) :
            return GradedExpansionRing_class( self.__base_gen_expansions, self.__gen_expansions,
                                              rel, self.__grading, self.__all_relations, self.__reduce_before_evaluating )
        elif isinstance(self.__gen_expansions.universe(), Module) :
            return GradedExpansionModule_class( self.__base_gen_expansions, self.__gen_expansions,
                                                rel, self.__grading, self.__all_relations, self.__reduce_before_evaluating )

        raise RuntimeError( "The generators' universe must be an algebra or a module." )
        
    def __cmp__(self, other) :
        """
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: funct = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct == GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            True
            sage: funct == GradedExpansionFunctor(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,3)))
            False
            sage: P.<a,b> = PolynomialRing(QQ)
            sage: funct == GradedExpansionFunctor(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), P.ideal(a^2 - b), DegreeGrading((1,2)))
            False
            sage: funct == GradedExpansionFunctor(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 4}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            False
            sage: funct == GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1 : 4}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b', 'c']).ideal(0), DegreeGrading((1,2,2)))
            False
        """
        c = cmp(type(self), type(other))
        if c == 0 :
            c = cmp(self.__relations, other.__relations)
        if c == 0 :
            c = cmp(self.__all_relations, other.__all_relations)
        if c == 0 :
            c = cmp(self.__grading, other.__grading)
        if c == 0 :
            c = cmp(self.__base_gen_expansions, other.__base_gen_expansions)
        if c == 0 :
            c = cmp(self.__gen_expansions, other.__gen_expansions)
            
        return c

    def merge(self, other) :
        """
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: funct = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct.merge(funct) is None
            False
            sage: funct2 = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((3,2)))
            sage: funct.merge(funct2) is None
            True
            sage: funct2 = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 2}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct.merge(funct2) is None
            True
            sage: K.<rho> = CyclotomicField(6)
            sage: funct2 = GradedExpansionFunctor(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(K, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: funct2.merge(funct) is None
            False
        """
        #TODO: Implement merging of base rings
        if self == other :
            return self
        
        if self.__all_relations != other.__all_relations or \
           self.__grading != other.__grading or \
           self.__base_gen_expansions != other.__base_gen_expansions or \
           self.__gen_expansions != other.__gen_expansions :
            return None
        
        if self.__relations.ring().has_coerce_map_from(other.__relations.ring()) and \
           self.__relations == self.__relations.ring().ideal(other.__relations.gens()) :
            return self
            
        return None
    
#===============================================================================
# GradedExpansionBaseringInjection
#===============================================================================

class GradedExpansionBaseringInjection ( Morphism ) :
    """
    The injection of the base ring into a ring of graded expansions.
    """
    
    def __init__(self, domain, codomain ) :
        """
        INPUT:
            - ``domain``   -- A ring.
            - ``codomain`` -- A ring of graded expansions.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: GradedExpansionBaseringInjection(QQ, ger)
            Base ring injection of Graded expansion ring with generators a, b morphism:
              From: Rational Field
              To:   Graded expansion ring with generators a, b
        """
        Morphism.__init__(self, domain, codomain)
        
        self._repr_type_str = "Base ring injection of %s" % (codomain,)

    def _call_(self, x) :
        """
        INPUT:
            - `x` -- An element of the domain.
        
        OUTPUT:
            An element of the codomain.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: inj = GradedExpansionBaseringInjection(ger.base_ring(), ger)
            sage: inj(ger.base_ring()(2))
            Graded expansion 2
        """
        return self.codomain()._element_constructor_(x)
            
    def _call_with_args(self, x, *args, **kwds):
        """
        INPUT:
            - `x`      -- An element of the domain.
            - `args``  -- Will be forwarded to the codomain's element constructor. 
            - ``kwds`` -- Will be forwarded to the codomain's element constructor.
        
        OUTPUT:
            An element of the codomain.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: inj = GradedExpansionBaseringInjection(ger.base_ring(), ger)
            sage: h = inj(ger.base_ring()(0))
        """
        return self.codomain()._element_constructor_(x, *args, **kwds)

#===============================================================================
# GradedExpansionEvaluationHomomorphism
#===============================================================================

class GradedExpansionEvaluationHomomorphism ( Morphism ) :
    """
    The evaluation of a polynomial by substituting the Fourier expansions
    attached to a ring or module of graded expansions.
    """
    
    def __init__(self, relations, base_ring_images, images, codomain, reduce = True) :
        """
        INPUT:
            - ``relations``        -- An ideal in a polynomial ring.
            - ``base_ring_images`` -- A list or sequence of elements of a ring of (equivariant)
                                      monoid power series.
            - ``images``           -- A list or sequence of monoid power series.
            - ``codomain``         -- An ambient of (equivariant) monoid power series.
            - ``reduce``           -- A boolean (default: ``True``); If ``True`` polynomials will
                                      be reduced before the substitution is carried out.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ev = GradedExpansionEvaluationHomomorphism(PolynomialRing(QQ, ['a', 'b']).ideal(0), Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), mps, False)
        """
        self.__relations = relations
        self.__base_ring_images = base_ring_images
        self.__images = images
        self.__reduce = reduce
        
        Morphism.__init__(self, relations.ring(), codomain)

        self._repr_type_str = "Evaluation homomorphism from %s to %s" % (relations.ring(), codomain)

    def _call_with_args(self, x, *args, **kwds) :
        """
        SEE:
            :meth:~`._call_`.
        
        NOTE:
            ``args`` and ``kwds`` will be ignored.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: P.<a,b> = QQ[]
            sage: ev = GradedExpansionEvaluationHomomorphism(P.ideal(0), Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), mps, False)
            sage: h = ev(a, h = True)
        """
        return self._call_(x)
    
    def _call_(self, x) :
        """
        INPUT:
            - `x` -- A polynomial.
        
        OUTPUT:
            An element of the codomain.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: P.<a,b> = QQ[]
            sage: ev = GradedExpansionEvaluationHomomorphism(P.ideal(0), Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), mps, False)
            sage: ev(a)
            Monoid power series in Ring of monoid power series over NN
            sage: ev = GradedExpansionEvaluationHomomorphism(P.ideal(a - b), Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), mps, True)
            sage: ev(a - b).coefficients()
            {0: 0}
        """
        if self.__reduce :
            x = self.__relations.reduce(x)
        
        ## Be careful not to directly substitute the elements of self.__images
        ## into the polynomial since they might be vectors, hence yielding
        ## an exception.
            
        #=======================================================================
        # if len(self.__base_ring_images) == 0 :
        #    parent = self.__images.universe()
        #    res = parent(0)
        #    
        #    for imexps,c in x.dict().iteritems() :
        #        if isinstance(imexps, int) :
        #            imexps = (imexps,)
        #        imexps = tuple(imexps)
        #        
        #        if imexps.count(0) == len(imexps) :
        #            res = res + c * parent(Integer(1))
        #        # this is the typical module case with an action
        #        # that does not respect the monoid structure
        #        elif imexps.count(0) == len(imexps) - 1 :
        #            i,e = dropwhile(lambda (_,e) : e == 0, enumerate(imexps)).next()
        #            if e == 1 :
        #                res = res + c * self.__images[i]
        #            else :
        #                res = res + c * self.__images[i]**e
        #        else :
        #            res = res + prod(map(operator.pow, self.__images, imexps))
        #            
        #    return res
        #=======================================================================
                
        expansion_ambient = self.__images.universe()
        res = self.__images.universe().zero_element()
        
        coeffs = x.dict()
        xexps = groupby( sorted(x.exponents()),
                         lambda e: ([e] if isinstance(e, int) else list(e))[len(self.__base_ring_images):] )
        
        for imexps, exps in xexps :
            factor = self.__base_ring_images.universe().zero_element()
            for e in exps :
                factor = factor + coeffs[e] * prod(map( operator.pow, self.__base_ring_images,
                                                        ([e] if isinstance(e,int) else e)[:len(self.__base_ring_images)] ))
            
            imexps = tuple(imexps)
                
            if imexps.count(0) == len(imexps) :
                res = res + factor * expansion_ambient.one_element()
            elif imexps.count(0) == len(imexps) - 1 :
                i,e = dropwhile(lambda (_,e) : e == 0, enumerate(imexps)).next()
                # this is the typical module case with an action
                # that does not respect the monoid structure
                if e == 1 :
                    res = res + factor * self.__images[i]
                else :
                    res = res + factor * self.__images[i]**e
            else :
                res = res + factor * prod(map(operator.pow, self.__images, imexps))
                            
        return res
